package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.Arrays;

/**
 * 描述：
 * 给你一个 有序 数组 nums ，它由 n 个非负整数组成，同时给你一个整数 maximumBit 。你需要执行以下查询 n 次：
 * <p>
 * 找到一个非负整数 k < 2maximumBit ，使得 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k 的结果 最大化 。k 是第 i 个查询的答案。
 * 从当前数组 nums 删除 最后 一个元素。
 * 请你返回一个数组 answer ，其中 answer[i]是第 i 个查询的结果
 * <p>
 * XOR
 * <p>
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-xor-for-each-query
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author 🧑 ‍wanwei
 * @since 2023-01-14 11:08
 */
public class CT1829 {
    public static void main(String[] args) {
        int[] nums = {2,3,4,7};
        int maximumBit = 3;

        int[] maximumXor = getMaximumXor(nums, maximumBit);
        System.out.println(Arrays.toString(maximumXor));
    }


    /**
     * 先算出 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] 再选择出合适的k
     * 1.避免重复计算异或值
     * <p>
     * 没什么技巧-只要会算第一个 后面的照着相同的逻辑实现 即可
     * 异或运算-》同位值不一样 异或得到的值越大
     *
     * @param nums
     * @param maximumBit
     * @return
     */
    public static int[] getMaximumXor(int[] nums, int maximumBit) {
        int[] arrays = new int[nums.length];

        int value = 0;
        for (int i = 0; i < nums.length; i++) {
            value = value ^ nums[i];
            arrays[arrays.length - 1 - i] = getMax(value, maximumBit);
        }
        return arrays;
    }

    /**
     * 找到一个小于2*maximumBit的值 使x与其异或的值最大
     * <p>
     * 1.如果 先计算x的每一位值 然后反向取值算出k值
     * 其中k的值小于2*maximumBit
     *
     * @param x
     * @param maximumBit
     * @return
     */
    private static int getMax(int x, int maximumBit) {
        int kMax = (int) Math.pow(2, maximumBit);
        int max = x > kMax ? x : kMax;

        //取幂值
        int length = (int) (Math.log(max) / Math.log(2));
        //转二进制
        String binary = Integer.toString(x, 2);

        int k = 0;
        for (int j = 0; j < length; j++) {
            int value = k;
            if (j >= binary.length()) {
                value = k + (int) Math.pow(2, j);
            } else {
                char c = binary.charAt(binary.length() - 1 - j);
                if (c == '0') {
                    value = k + (int) Math.pow(2, j);
                }
            }
            if (value >= kMax) {
                break;
            }
            k = value;
        }
        return k;
    }
}
